package cn.hesion.dataStructures.BTree;
/**
 * ClassName: BTree <br/>
 * Description: <br/>
 * date: 2021/12/10 22:22<br/>
 *
 * @author Hesion<br />
 * @version
 * @since JDK 1.8
 */

/**
 * B树 自己的思路写的B树
 *
 * @author: hesion
 * @create: 2021-12-10 22:22
 **/
public class BTreeSeff {

    //根节点
    BTreeNode root;

    //定义了树的最大阶t
    //定义了最多的子节点个数
    int t;

    public BTreeSeff(int t) {
        this.root = null;
        this.t = t;
    }


    // function to traverse the tree
    public void traverse() {
        if (this.root != null)
            this.root.traverse();
        System.out.println();
    }

    // function to search a key in this tree
    public BTreeNode search(int k) {
        if (this.root == null)
            return null;
        else
            return this.root.search(k);
    }

    class BTreeNode {
        //保存key的数据
        int[] keys;

        //最小的度
        int t;
        //存储孩子节点
        BTreeNode[] C;
        //当前有多少keys
        int n;
        //需要标记这个节点是不是叶子节点
        boolean leaf;

        //构造函数，进行节点初始化

        public BTreeNode(int t, boolean leaf) {
            this.keys = new int[2 * t - 1];
            this.t = t;
            this.C = new BTreeNode[2 * t];
            this.leaf = leaf;
            this.n = 0;
        }

        //实现遍历方法
        public void traverse() {
            //for循环遍历
            int i = 0;
            for (i = 0; i < n; i++) {
                //判断遍历到的节点是不是叶子节点
                if (leaf == false) {
                    //递归调用
                    C[i].traverse();
                }
                //是叶子节点就打印
                System.out.print(keys[i] + " ");
            }

            // 打印最开始进入的节点的值
            if (leaf == false)
                C[i].traverse();
        }

        public BTreeNode search(int k) {
            int i = 0;

            while (i < n && k > keys[i]) {
                i++;
            }
            //代码运行到这，此时的i所指向的keys[i]
            //要么表示的是我们要找的key
            //要么就是叶子节点，也就是没有找到
            if (keys[i] == k) {
                return this;
            }
            //如果此时的节点是叶子节点
            //表示该k不在这棵树中
            if (this.leaf == true) {
                return null;
            }
            //否则，递归搜索
            return C[i].search(k);
        }

        /**
         *
         * @param i
         * @param y
         */
        public void splitChild(int i, BTreeNode y) {
            BTreeNode z = new BTreeNode(y.t, y.leaf);
            z.n = t - 1;

            //将y中倒数t-1个key，放入到z中
            for (int j = 0; j < t - 1; j++) {
                z.keys[j] = y.keys[j + t];
            }

            if (!y.leaf) {
                for (int j = 0; j < t; j++) {
                    z.C[j] = y.C[j + t];
                }
            }
            //将y的n置为最小度
            y.n = t - 1;
            //既然已经拆分了两个孩子，那么z需要变成新root的子节点
            //腾位置
            for (int j = n; j >= i + 1; j--) {
                C[j + 1] = C[j];
            }
            //放入
            C[i + 1] = z;

            //keys里也有需要腾位置,如果该节点没有元素的话，该循环并不会执行
            for (int j = n - 1; j >= i; j--) {
                keys[j + 1] = keys[j];
            }
            keys[i] = y.keys[t - 1];

            //将当前key的数量增加1
            n = n + 1;
        }

        public void insertNonFull(int k) {
            //找到最右边元素的坐标
            int i = n - 1;

            //如果他是叶子节点就直接插入
            if (leaf) {
                //循环插入，找到元素合适的插入位置,还需要腾位置
                //因为不知道具体要执行多少次才能找到那个位置，所采用while
                while (i >= 0 && keys[i] > k) {
                    keys[i + 1] = keys[i];
                    i--;
                }
                keys[i + 1] = k;
                n = n + 1;
            } else {
                //while循环去找到那个i，不做挪位操作。
                while (i >= 0 && keys[i] > k) {
                    i--;
                }

                //循环结束，表示已经找到了那个位置
                //判断一下这个节点的元素是否满了
                if (C[i + 1].n == 2 * t - 1) {
                    splitChild(i + 1, C[i + 1]);

                    if (keys[i + 1] < k) {
                        i++;
                    }
                }
                C[i + 1].insertNonFull(k);
            }

        }
    }

    public void insert(int k) {
        //判断一下根节点是不是空的
        //如果是空的就是初始化一个节点
        if (root == null) {
            root = new BTreeNode(t, true);
            root.keys[0] = k;
            root.n = 1;
        } else {
            //根节点不为空，判断是否full、 满了
            if (root.n == 2 * t - 1) {
                //将要进行拆分，创建一个新的根节点出来。
                //这里就可以看出B树是向上生长的
                BTreeNode s = new BTreeNode(t, false);
                s.C[0] = root;

                s.splitChild(0, root);

                //节点已经被拆分了,现在要进行k的插入
                int i = 0;
                //此时的s是根节点，我先和根节点对比下，是不是比根节点的key打
                //如果大，那么找到他的子节点去插入，

                if (s.keys[0] < k) {
                    i++;
                }
                //执行插入操作
                s.C[i].insertNonFull(k);

                //将root 指向s
                root = s;
            } else {
                root.insertNonFull(k);
            }
        }



    }

    public static void main(String[] args) {
        BTreeSeff t = new BTreeSeff(3);
        t.insert(10);
        t.insert(20);
        t.insert(5);
        t.insert(6);
        t.insert(12);
        t.insert(30);
        t.insert(7);
        t.insert(17);

        t.traverse();
        System.out.println("-------------------------");
        BTreeNode res = t.search(17);
        if(res != null){
            for (int key : res.keys) {
                System.out.print("key="+key+" ");
            }
        }
    }
}

